package Year22_Month04.day14;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 最小覆盖子串 {
    public String minWindow(String s, String t) {
        int left = 0;//定义最后的左指针下标
        int right = 0;//定义最后的右指针下标
        int leftNow = 0;//当前的当前的左指针下标，用来求最小子串
        int count = 0;//用来控制窗口的滑动
        int minSize = Integer.MAX_VALUE;//记录最小子串的长度
        Map<Character,Integer> map = new HashMap<>();//用一个map表来映射对应的字符出现次数
        for(Character c:t.toCharArray()){
            //统计字符出现的次数
            map.put(c,map.getOrDefault(c,0) + 1);
        }
        for (int rightNow = 0; rightNow < s.length(); rightNow++) {
            Character c = s.charAt(rightNow);
            if(map.containsKey(c)){
                //记录当前字符对应的value值
                int cnt = map.get(c);
                map.put(c,cnt - 1);
                //如果cnt - 1 == 0，那就证明当前这个字符已经完全的在子串当中
                if(cnt == 1) count++;
            }
            //能进入while循环，就证明当前字符已经完全在子串中了
            while(count >= map.size()){
                //这个时候就要判断一下要不要更新子串
                if(minSize > (rightNow - leftNow + 1)){
                    right = rightNow;
                    left = leftNow;
                    minSize = right - left + 1;
                }
                Character rightC = s.charAt(leftNow);
                if(map.containsKey(rightC)){
                    int cnt = map.get(rightC);
                    map.put(rightC,cnt + 1);
                    //如果说cnt == 0，那就意味着什么呢？意味着原先字符是完全在子串中的，经过下面的leftNow++后就不在了
                    if(cnt == 0){
                        count--;
                    }
                }
                leftNow++;
            }

        }
        return minSize == Integer.MAX_VALUE ? "" : s.substring(left,right+1);
    }
}
